package com.lw.leetcode.bingChaJi.c;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

/**
 * Created with IntelliJ IDEA.
 * 952. 按公因数计算最大组件大小
 *
 * @author liw
 * @version 1.0
 * @date 2022/7/30 15:43
 */
public class LargestComponentSize {


    public static void main(String[] args) {
        LargestComponentSize test = new LargestComponentSize();

        // 4
//        int[] arr = {4, 6, 15, 35};

        // 2
//        int[] arr = {20, 50, 9, 63};

        // 8
        int[] arr = {2, 3, 6, 7, 4, 12, 21, 39};

        int i = test.largestComponentSize(arr);
        System.out.println(i);
    }


    private Map<Integer, Integer> map;
    private int[] items;

    public int largestComponentSize(int[] nums) {
        int m = (int) Math.pow(100000, 0.5);
        int length = nums.length;
        this.map = new HashMap<>();
        this.items = new int[length];
        for (int i = 0; i < length; i++) {
            items[i] = i;
        }
        for (int i = 0; i < length; i++) {
            int num = nums[i];
            if (num == 1) {
                continue;
            }
            List<Integer> list = getList(num, m);
            for (int v : list) {
                Integer t = map.get(v);
                if (t == null) {
                    map.put(v, i);
                } else {
                    int a = find(t);
                    int b = find(i);
                    if (a != b) {
                        items[b] = a;
                    }
                }
            }
        }
        Map<Integer, Integer> counts = new HashMap<>();
        int max = 0;
        for (int item : items) {
            int k = find(item);
            int i = counts.getOrDefault(k, 0) + 1;
            max = Math.max(max, i);
            counts.put(k, i);

        }
        return max;
    }

    private int find(int t) {
        if (items[t] == t) {
            return t;
        }
        items[t] = find(items[t]);
        return items[t];
    }

    private List<Integer> getList(int num, int m) {
        int i = 2;
        List<Integer> list = new ArrayList<>();
        while (i <= m && num > 1) {
            if (num % i == 0) {
                num /= i;
                list.add(i);
            } else {
                i++;
            }
        }
        if (num > 1) {
            list.add(num);
        }
        return list.stream().distinct().collect(Collectors.toList());
    }

}
